package com.example.hot100;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 *  示例 1:
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 *
 *  示例 2:
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 *
 *  示例 3:
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 */
public class Leetcode739_DailyTemperatures {
    public static void main(String[] args) {
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] res = new Solution().dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(res));
    }

    static class Solution {
        /**
         * 解法三：单调栈
         * @param temperatures
         * @return
         */
        private int[] dailyTemperatures3(int[] temperatures) {
            int[] res = new int[temperatures.length];
            Deque<Integer> stack = new LinkedList<>();// 存储temperatures的索引值，从栈底到栈顶temperature[stack[m]]单减
            for (int i = 0; i < temperatures.length; i++) {
                int curTemper = temperatures[i];
                while (!stack.isEmpty() && curTemper > temperatures[stack.peek()]) {
                    int prevIndex = stack.pop();
                    res[prevIndex] = i - prevIndex;
                }
                stack.push(i);
            }
            return res;
        }

        /**
         * 暴力解法二：参见官网题解
         * https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/
         * @param temperatures
         * @return
         */
        private int[] dailyTemperatures2(int[] temperatures) {
            int[] res = new int[temperatures.length];
            int[] next = new int[101];// next[i] = m 代表温度为 i 的第一次出现的天数是 m
            Arrays.fill(next, Integer.MAX_VALUE);
            for (int i = temperatures.length - 1; i >= 0; i--) {
                int curTemper = temperatures[i];
                int warmerIndex = Integer.MAX_VALUE;
                for (int j = curTemper + 1; j < next.length; j++) {
                    if (next[j] < warmerIndex) warmerIndex = next[j];
                }

                if (warmerIndex < Integer.MAX_VALUE) res[i] = warmerIndex - i;

                next[temperatures[i]] = i;
            }
            return res;
        }

        /**
         * 暴力法
         * @param temperatures
         * @return
         */
        private int[] dailyTemperatures1(int[] temperatures) {
            int[] res = new int[temperatures.length];

            for (int i = 0; i < temperatures.length; i++) {
                int j = i + 1;
                while (j < temperatures.length && temperatures[j] <= temperatures[i])
                    j++;
                res[i] = j == temperatures.length ? 0 : j - i;
            }

            return res;
        }

        public int[] dailyTemperatures(int[] temperatures) {
            return dailyTemperatures1(temperatures);
        }
    }
}
